package com.leetcode.剑指Offer;

import java.util.Arrays;

/**
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 * 
 * @author LZF
 *
 */
public class Offer30包含min函数的栈 {

}
/**
 * 题目要求三种操作都要O(1)，push和pop操作就比较简单
 * 我们用数组当作底层存储结构，那只需要保存 指向尾部数据的指针 就可以实现push和pop
 * 而对于min函数来说，要实现O(1)，就也必须时刻保存最小值
 * 但是不能只保存出现过的最小值，因为这个最小值有可能要被pop出去
 * 那怎么办呢？
 * 只能再借助一个数组，来保存当尾部指针指向哪里的时候，哪里就是最小值
 * 比如说，尾部指针tail=3，表示container[tail]就是栈顶的元素，对应的minStack[tail]就是当前的最小值
 * 尾部指针tail初始化是-1，所以返回最小值我们不能直接返回minStack[tail]，有可能会越界。
 * 需要用一个minVal来时刻保存最小值，当栈没有元素的时候，需要返回什么，根据需要给minVal指定初始值
 * 这里题目没有提及，因为题目保证至少栈至少存在一个元素，所以我们初始minVal为int的最大值
 * @author LZF
 *
 */
class MinStack {
	/** 底部存储结构：数组*/
	int[] container;
	/** 存储最小值的数组*/
	int[] minStack;
	/** 保存最小值*/
	int minVal;
	/** 底部容器的大小 */
	int size;
	/** 尾部指针*/
	int tail;

	/** initialize your data structure here. */
	public MinStack() {
		container = new int[20];
		minStack = new int[20];
		size = 20;//初始化容器的大小为20
		minVal = Integer.MAX_VALUE;//初始化minVal为int的最大值
		tail = -1;//初始化尾部指针
	}

	public void push(int x) {
		//当尾部指针到达size时，需要扩容，扩容机制就是扩当前size的两倍
		if (tail == size - 1) {
			container = Arrays.copyOf(container, size * 2);
			minStack = Arrays.copyOf(minStack, size * 2);
			size *= 2;
			container[++tail] = x;
		} else {
			container[++tail] = x;
		}
		minVal = Math.min(minVal, x);
		minStack[tail] = minVal;
	}
	
	public void pop() {
		//出栈的时候，需要更新最小值，注意tail的越界
		if (tail == 0) {
			tail--;
			minVal = Integer.MAX_VALUE;//当栈没有元素，最小值初始化为int的最大值
		} else if (tail > 0) {
			tail--;
			minVal = minStack[tail];
		}
	}

	public int top() {
		return container[tail];
	}

	public int min() {
		return minVal;
	}

}

/**
 * Your MinStack object will be instantiated and called as such: MinStack obj =
 * new MinStack(); obj.push(x); obj.pop(); int param_3 = obj.top(); int param_4
 * = obj.min();
 */